Search Results

1. E. Hyytiä, Lookahead Actions in Dispatching to Parallel Queues, Performance Evaluation, 2013, Vienna, Austria, (IFIP Performance'13) (link)(bib)

   Abstract: Applying the first policy iteration (FPI) to any static dispatching (task assignment) policy yields a new improved dynamic policy that takes into account the particular cost structure and the expected future arrivals. However, it is generally hard to go beyond that due to the complex state space and the resulting difficulty in computing the value function for a dynamic policy. For example, applying FPI to identical FCFS servers with Bernoulli split gives the least-work-left (LWL) policy, for which no closed-form value function is known. In fact, such a dispatching system with LWL is equivalent to an M/G/k queue, the performance measures of which have remained as an open problem. With heterogeneous servers the situation becomes even more complicated. In this paper, we take an intermediate approach and consider lookahead actions that concern not only the current job but also the job arriving next, after which a basic (static) policy is assumed to take over. This enables sound estimates for marginal admission costs, e.g., with respect to LWL and Myopic, yielding new near-optimal dispatching policies, which are shown to outperform several previously proposed policies in the numerical example cases.